#include<vector>
#include<unordered_set>
using namespace std;

class Solution {
private:
    bool dfs(int source, int target, unordered_set<int>& visited, const vector<unordered_set<int>>& graph) {
        if (source == target)
            return true;
        visited.insert(source);
        for (auto next : graph[source]) {
            if (visited.find(next) != visited.end())
                continue;
            if (dfs(next, target, visited, graph))
                return true;
        }
        return false;

    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        vector<unordered_set<int>>graph(edges.size()+1);
        for (auto& edge : edges) {
            unordered_set<int> visited;
            if (dfs(edge[0], edge[1], visited, graph))
                return edge; 
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }
        return {};
    }
};


//class Solution {
//private:
//    int findParent(int x, vector<int>& p) {
//        return p[x] == x ? x : (x = findParent(p[x], p));
//    }
//    bool isSameParent(int x, int y, vector<int>& p) {
//        int px = findParent(x, p);
//        int py = findParent(y, p);
//        p[px] = py;
//        return px == py;
//    }
//
//
//public:
//    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
//        vector<int>parents(edges.size() + 1);
//        for (int i = 0; i < parents.size(); ++i)
//            parents[i] = i;
//        for (auto& edge : edges) {
//            if (isSameParent(edge[0], edge[1], parents))
//                return edge;
//        }
//        return {};
//    }
//};